package baseclass.d_list;


import utils.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @date 2020/2/28 21:22
 */
public class Code08_判断两个单向无环链表是否相交 {
    //如果相交找出第一个交点
    public static ListNode hasCommon1(ListNode head1, ListNode head2){
        if(head1 == null || head2 == null) return null;
        Set<ListNode> set = new HashSet<>();
        ListNode p1 = head1;
        while (p1 != null){
            set.add(p1);
            p1 = p1.next;
        }
        p1= head2;
        while (p1 != null){
            if(set.contains(p1)) return p1;
            p1 = p1.next;
        }
        return null;
    }
    /**
     * 方式2：两个单项无环链表相交，则必定从第一个交点到尾巴 都是同一部分
     * 统计两个链表长度 l1,l2。
     * 让长的先走 abs(l2 -l1)，然后一起走，剩下的相同必定会一起走到第一个公共节点，
     */
    public static ListNode hasCommon2(ListNode head1, ListNode head2){
        if(head1 == null || head2 == null) return null;
        int len1 = getListLength(head1);
        int len2 = getListLength(head2);
        ListNode p2;
        ListNode p1;
        int count = Math.abs(len1 - len2);
        p1 = head1;
        p2 = head2;
        if(len1 > len2){
            while (count-- != 0) p1 = p1.next;
        }else {
            while (count-- != 0) p2 = p2.next;
        }
        while (p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1; //包括p1 == null
    }

    /**
     * 方式3：两个链表从尾巴开始走，一直是重复的，最后一个重复的就是第一个
     * 相交节点
     */

    private static int getListLength(ListNode head2) {
        int len2 = 1;
        ListNode p2 = head2;
        while (p2.next != null){
            p2 = p2.next;
            len2 ++;
        }
        return len2;
    }
}
